package com.fr.lintcode;

import java.util.ArrayList;
import java.util.List;

import org.junit.Test;

/**
*作者：furong
*日期：2017年2月8日
*时间：上午9:53:28
*/
public class Q104 {
    /**
     * @param lists: a list of ListNode
     * @return: The head of one sorted list.
     */
    public ListNode mergeKLists(List<ListNode> lists) {
        ListNode rs = null;
        ListNode tmp = null;
        if (lists == null || lists.size() <= 0) {
            return rs;
        }
        int length = lists.size();
        boolean hasData = true;
        while (hasData) {
            hasData = false;
            int min = 0;
            for (int i = 1; i < length; i++) {
                ListNode l = lists.get(i);
                if (l != null) {
                    hasData = true;
                    ListNode lmin = lists.get(min);
                    if (lmin == null) {
                        min = i;
                    } else {
                        if (l.val < lmin.val) {
                            min = i;
                        }
                        hasData = true;
                    }
                }
            }
            ListNode lmin = lists.get(min);
            if (lmin != null) {
                if (rs == null) {
                    rs = lmin;
                    tmp = rs;
                } else {
                    tmp.next = lmin;
                    tmp = tmp.next;
                }
                lmin = lmin.next;
                lists.remove(min);
                lists.add(lmin);
            } else {
                break;
            }
        }
        return rs;
    }

    @Test
    public void testA() {
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(2);
        ListNode l3 = new ListNode(3);
        ListNode l4 = new ListNode(4);
        l1.next = new ListNode(2);
        List<ListNode> lists = new ArrayList<>();
        lists.add(l1);
        lists.add(l2);
        lists.add(l3);
        lists.add(l4);
        System.out.println(mergeKLists(lists));
    }
}
